#include "stdio.h"
#include "stdlib.h"

#define MaxSize 100
#define InitSize 100

struct ElemType{
	char c;
	int n;
};

typedef struct LNode{
	ElemType data;
	LNode* next;
}*LinkStack;

void init(LinkStack &S);
void destory(LinkStack &S);

void push(LinkStack &S,ElemType e);
void pop(LinkStack &S,ElemType &e);

void getTop(LinkStack &S,ElemType &e);
bool isEmpty(LinkStack S);

//   ((15 / (7 - ( 1 + 1 ))) * 3 ) - ( 2 + ( 1 + 1 ))
// "操作数、运算符、界限符"

char* infixesConvertToSuffixes(char* s,int length);
int priority(char a);

int suffixesCalculate(char* s);
int calcuate(int a,int b,char operation);

int main(){
//	char *p=(char*)"";
	char s[] = "(1+2)*5+3*5+1";
	char *p = infixesConvertToSuffixes(s,sizeof(s));
	printf("%s\n",p);
	int result = suffixesCalculate(p);
	printf("%d\n",result);
	free(p);
	return 0;
}

int calcuate(int a,int b,char operation){
	switch(operation){
		case '+': return a+b;
		case '-': return a-b;
		case '*': return a*b;
		case '/': return a/b;
	}
	return 0;
}

int suffixesCalculate(char* s){
	int j=0;
	LinkStack N;
	init(N);
	ElemType e,t;
	while(s[j]!='\0'){
//		printf("%c",s[j]);
		if(s[j] <= '9' && s[j] >= '0'){
			e.n = s[j]-48;
			push(N,e);
		}else{
			pop(N,e);
			pop(N,t);
//			printf(" %d ",t.n);
//			printf(" %d ",e.n);
			e.n=calcuate(t.n,e.n,s[j]);
//			printf(" %d ",e.n);
			push(N,e);
		}
		j++;
	}
	pop(N,e);
	return e.n;
}

int priority(char a){
	switch(a){
		case '+':return 1;
		case '-':return 1;
		case '*':return 2;
		case '/':return 2;
		case '(':return 10;
	}
	return 0;
}

char* infixesConvertToSuffixes(char* s,int length){

	LinkStack S;

	char *p=(char *)malloc(sizeof(char)*length);
	
	init(S);
	int i=0,j=0;
	ElemType e;
	while(s[j]!='\0'){
		// 操作数
		if(s[j] <='9' && s[j] >='0'){
			p[i++]=s[j];
//			printf("%c",s[j]);
		}
		//界限符
		else if(s[j]=='('){
			e.c = '(';
			push(S,e);
		}else if(s[j]==')'){
			getTop(S,e);
			while(e.c!='('){
				pop(S,e);
				p[i++]=e.c;
//				printf("%c",e.n);
				getTop(S,e);
			}
			pop(S,e);
		}
		// 运算符
		else if(s[j]=='+' || s[j]=='-' || s[j]=='*' || s[j]=='/'){
//			printf("%c",s[j]);
//			printf("%d",isEmpty(S));
			if(!isEmpty(S)){
				getTop(S,e);
//				printf(" %c ",e.n);
				while(priority(e.c)>= priority(s[j]) && e.c!='(' ){
//					printf("%c",e.n);
					pop(S,e);
					p[i++]=e.c;
//					printf("%c",e.n);
					if(!isEmpty(S))
						getTop(S,e);
					else
						break;
				}
//				printf(" %d ",isEmpty(S));
			}
			e.c = s[j];
			push(S,e);
//			printf("%c",e.n);
			
		}else
			return NULL;
		j++;
	}
	while(!isEmpty(S)){
		pop(S,e);
		p[i++]=e.c;
	}
	p[i]='\0';
	destory(S);
	return p;
}

void init(LinkStack &S){
	S = (LNode* )malloc(sizeof(LNode));
	S->next=NULL;
}

void destory(LinkStack &S){
	ElemType e;
	while(!isEmpty(S))
		pop(S,e);
	free(S);
}

bool isEmpty(LinkStack S){
	if(S->next==NULL)
		return true;
	return false;
}

void push(LinkStack &S,ElemType e){
	
	LNode* p = (LNode*)malloc(sizeof(LNode));
	p->data = e;
	p->next = S->next;
	S->next = p;
	
}

void pop(LinkStack &S,ElemType &e){
	if(isEmpty(S))
		return;
	e = S->next->data;
	S->next = S->next->next;
}

void getTop(LinkStack &S,ElemType &e){
	e = S->next->data;
}















